package demo.practice.leetcode_offer;

public class Offer13 {


    public int movingCount(int m, int n, int k) {
        int[][] square = new int[m][n];
        return back(0, 0, k, square);
    }


    public int back(int i, int j, int k, int[][] square) {
        if (i >= 0 && i < square.length && j >= 0 && j < square[i].length) {
            int res = 0;
            if (check(square, i, j, k)) {
                res += 1;
                square[i][j] = 1;
                res += back(i + 1, j, k, square);
                res += back(i - 1, j, k, square);
                res += back(i, j + 1, k, square);
                res += back(i, j - 1, k, square);
            }
            return res;
        }
        return 0;
    }

    private boolean check(int[][] square, int i, int j, int k) {
        if (square[i][j] == 1)
            return false;
        return countDigit(i) + countDigit(j) <= k;
    }


    private int countDigit(int num) {
        int res = 0;
        while (num > 0) {
            res += num % 10;//
            num = num / 10;
        }
        return res;
    }
}
